package com.future.interview;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * Description: 面试题40. 最小的k个数
 * 输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。
 * 示例 1：
 * 输入：arr = [3,2,1], k = 2
 * 输出：[1,2] 或者 [2,1]
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/zui-xiao-de-kge-shu-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @author weiruibai.vendor
 * Date: 2022/7/23 10:05
 */
public class Solution_40 {

    public static void main(String[] args) {
        BitMap bitMap = new BitMap(10);
        System.out.println(bitMap.isContains(1));
        bitMap.add(1);
        System.out.println(bitMap.isContains(1));
        bitMap.add(2);
        System.out.println(bitMap.isContains(2));
        bitMap.delete(2);
        System.out.println(bitMap.isContains(2));
        bitMap.add(5);
        System.out.println("=================");
        int[] arr = new int[]{3, 2, 1};
        int k = 2;
        arr = new int[]{0, 1, 2, 1};
        /**
         *
         * 75
         */
        arr = new int[]{0, 0, 1, 2, 4, 2, 2, 3, 1, 4};
        k = 8;
        arr = new int[]{0, 1, 1, 1, 4, 5, 3, 7, 7, 8, 10, 2, 7, 8, 0, 5, 2, 16, 12, 1, 19, 15, 5, 18, 2, 2, 22, 15, 8, 22, 17, 6, 22, 6, 22, 26, 32, 8, 10, 11, 2, 26, 9, 12, 9, 7, 28, 33, 20, 7, 2, 17, 44, 3, 52, 27, 2, 23, 19, 56, 56, 58, 36, 31, 1, 19, 19, 6, 65, 49, 27, 63, 29, 1, 69, 47, 56, 61, 40, 43, 10, 71, 60, 66, 42, 44, 10, 12, 83, 69, 73, 2, 65, 93, 92, 47, 35, 39, 13, 75};
        k = 75;
        Solution_40 solution = new Solution_40();
        int[] leastNumbers = solution.getLeastNumbers(arr, k);
        System.out.println(Arrays.toString(leastNumbers));
    }

    /**
     * @param arr
     * @param k
     * @return
     */
    public int[] getLeastNumbers(int[] arr, int k) {
        if (k == 0 || arr == null || arr.length == 0) {
            return new int[0];
        }
        /**
         * 一个数可能有重复几个，需要记录
         */
        Map<Integer, Integer> map = new HashMap<>();
        int[] ans = new int[k];
        int N = arr.length;
        int min = arr[0];
        int max = arr[0];
        for (int i = 0; i < N; i++) {
            map.put(arr[i], map.getOrDefault(arr[i], 0) + 1);
            max = Math.max(max, arr[i]);
            min = Math.min(min, arr[i]);
        }
        if (max == min) {
            for (int i = 0; i < k; i++) {
                ans[i] = arr[0];
            }
            return ans;
        }
        /**
         * 用位图存数据，依次标记
         */
        BitMap bitMap = new BitMap(max);
        for (Integer num : arr) {
            bitMap.add(num);
        }
        int index = 0;
        /**
         * 因为arr[i]>=0,所以从0开始遍历到max，看哪个数在位图中
         */
        for (int num = 0; num <= max && index < k; num++) {
            if (bitMap.isContains(num)) {
                int times = map.get(num);
                int tmp = index;
                for (; index < (tmp + times) && index < k; index++) {
                    ans[index] = num;
                }

            }
        }
        return ans;
    }
}

class BitMap {

    private long[] arr;

    public void add(int num) {
        int index = num >> 6;
        arr[index] = arr[index] | (1L << (num % 64));
    }

    public void delete(int num) {
        if (!isContains(num)) {
            return;
        }
        int index = num >> 6;
        arr[index] = arr[index] & (~(1L << (num % 64)));
    }

    public boolean isContains(int num) {
        int index = num >> 6;
        return (arr[index] & (1l << (num % 64))) != 0;
    }

    public BitMap(int max) {
        this.arr = new long[(max + 64) >> 6];
    }
}